package org.example.Greedy_Algorithm;

public class Monitoring_binary_trees {
    public static int  res = 0;
    public static void main(String[] args) {
        //监控二叉树

        //给定一个二叉树，我们在树的节点上安装摄像头。
        //节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
        //计算监控树的所有节点所需的最小摄像头数量。
        TreeNode node1 = new TreeNode(0);
        TreeNode node2 = new TreeNode(0);
        TreeNode node3 = new TreeNode(0);
        TreeNode node4 = new TreeNode(0);
        TreeNode node5 = new TreeNode(0);
        TreeNode root = new TreeNode(0);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(0);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node5.left = node7;
        int i = minCameraCover(root);
        System.out.println(i);
    }
    public static int minCameraCover(TreeNode root) {
        if (search(root)==0){
            res++;
        }
        return res;
    }
    public static int search(TreeNode root){
        if (root==null) return 2;
        int left = search(root.left);
        int right = search(root.right);
        if (left==2 && right==2){
            return 0;
        } else if (left == 0 || right == 0) {
            res++;
            return 1;
        }else {
            return 2;
        }

    }
}
